package com.hws.leetcode.Day_01_02;

import java.util.ArrayList;
import java.util.List;

/**
 * ClassName:leetcode_390
 * Package:com.hws.leetcode.Day_01_02
 * Description:
 *
 * @ date:2022/1/2 22:09
 * @ author:hws
 */
public class leetcode_390 {

    public int lastRemaining(int n) {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }
        while (list.size() > 1) {
            int leftSize = list.size();
            for (int i = 0; i < leftSize / 2; i++) {
                if (list.size() == 1){
                    return list.get(0);
                }
                list.remove(i);
            }
            if (leftSize % 2 == 1){
                list.remove(list.size() - 1);
            }
            if (list.size() == 1) {
                return list.get(0);
            } else {
                int rightSize = list.size();
                for (int i = (rightSize - 1) / 2; i >= 0; i--) {
                    if (list.size() == 1){
                        return list.get(0);
                    }
                    if (rightSize % 2 == 1){
                        list.remove(2 * i);
                    }else{
                        list.remove(2 * i + 1);
                    }
                }
            }
        }
        return list.get(0);
    }

    public static void main(String[] args) {
        leetcode_390 lc = new leetcode_390();
        System.out.println(lc.lastRemaining(13));
    }


}
